其他
自古帝王多短命，假如皇帝也懂负载均衡算法...
大家都知道古代皇帝各个都是后宫佳丽三千，而皇帝身上都天然的带着雨露均沾的精神，不想单独的宠爱一人！
图片来自 Pexels
弱水三千，又怎舍得只取一瓢饮？据传皇帝们晚上睡觉个个都怕冷，因此每晚都需要有人侍寝，那么这么多后宫，该翻谁牌子、怎么分配侍寝名额呢？
还别说，皇帝行房事竟还挺讲究的！早在《春秋》就有记载“晦阴惑疾，明谣心疾，以辟六气”。
九嫔以下，每九人中进御一人，八十一女御占九个晚上，世妇二十七人占三个晚上，九嫔占一个晚上，三夫人占一个晚上，以上共十四夜，皇后独占一个晚上，共十五夜。上半个月按上述安排进御，下半个月从十六日开始，由皇后起，再御九嫔、世妇、女御，与月亮由盛而衰相对应......
不同朝代的皇帝也有不同宠幸妃子的方法，著名的有羊车望幸、掷筛侍寝、蝶幸、翻牌悬灯等等。
不过在我看来，如果皇帝懂负载均衡算法的话，大可不必这么折腾，一套算法便可搞定终身侍寝大事！因此我们今天来介绍几种常用的负载均衡算法及代码实现！
先看下文章的大纲：
轮询算法
加权轮询算法
随机算法
加权随机算法
源地址 hash 算法
一致性 hash 算法
轮询算法
据史料记载，乾隆一生妃嫔就有 42 人，还不算大明湖畔的夏雨荷等在下江南时候留下的情。
/**
* *所有妃子集合
*/
public static final List<String> PRINCESS_LIST = Arrays.asList("令妃", "娴妃", "高贵妃", "纯妃");
然后从列表中轮询侍寝的妃子，用一个变量 index 去记录轮询的位置。
// 记录循环的位置
private static Integer index = 0;
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(getPrincess());
}
}
private static String getPrincess() {
// 超过数组大小需要归零（每次获取前判断，防止配置变化导致索引越界）
if (index >= PrincessConfig.PRINCESS_LIST.size()) {
index = 0;
}
String princess = PrincessConfig.PRINCESS_LIST.get(index);
index++;
return princess;
}
加权轮询算法
加权轮询就是可以主观的给每个妃子设置一个喜好值（权重值），以控制被选中的概率，因此我们需要定义如下的配置：
/**
* *所有妃子集合
*/
public static final Map<String, Integer> PRINCESS_MAP = new LinkedHashMap<String, Integer>() {
{
put("令妃", 5);
put("娴妃", 1);
put("高贵妃", 3);
put("纯妃", 2);
}
};
加权轮询实现一
然后我们去遍历这个 list，这样权重值越高，在 list 中出现的概率就越高，被轮询中的概率也就越高！
// 记录循环的位置
private static Integer index = 0;
public static void main(String[] args) {
for (int i = 0; i < 11; i++) {
System.out.println(getPrincess1());
}
}
private static String getPrincess1() {
// 遍历map放入到list中
List<String> princessList = new ArrayList<String>();
for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
int weight = PrincessConfig.PRINCESS_MAP.get(princess);
// 根据权重值重复放入到一个list中
for (int i = 0; i < weight; i++) {
princessList.add(princess);
}
}
if (index >= princessList.size()) {
index = 0;
}
String princess = princessList.get(index);
index++;
return princess;
}
输出结果如下：
加权轮询实现二
我们看具体代码实现：
// 记录循环的位置
private static Integer indexInteger = 0;
public static void main(String[] args) {
for (int i = 0; i < 11; i++) {
System.out.println(getPrincess2());
}
}
private static String getPrincess2() {
//记录总权重值
int totalWeight = 0;
for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
int weight = PrincessConfig.PRINCESS_MAP.get(princess);
totalWeight += weight;
}
// 归零
if (indexInteger >= totalWeight) {
indexInteger = 0;
}
int index = indexInteger;
String result = null;
for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
int weight = PrincessConfig.PRINCESS_MAP.get(princess);
// 落在当前区间 直接返回
if (index < weight) {
result = princess;
break;
}
// 没有落在当前区间 继续循环
index = index - weight;
}
indexInteger++;
return result;
}
输出结果与上面的方法一毛一样：
加权轮询实现三（平滑加权轮询）
动态权重值 dynamicWeight 初始为 0。
每次获取轮询获取目标妃子时先设置 dynamicWeight=dynamicWeight+weight。
然后找到所有妃子中动态权重值 dynamicWeight 最大的一个，则为本次轮询到的目标。
将本次轮询到的目标的 dynamicWeight 设置为 dynamicWeight-totalWeight(总权重值)。
这样看可能会有点不是很明白，我们来做个推算，假设我们还是有如下配置（配置中只有妃子名称及对应的权重值）：
/**
* *所有妃子集合
*/
public static final Map<String, Integer> PRINCESS_MAP = new LinkedHashMap<String, Integer>() {
{
put("令妃", 5);
put("娴妃", 1);
put("高贵妃", 3);
put("纯妃", 2);
}
};
①按照上面算法的第一点，在第一次轮询目标之前她们的 dynamicWeight 都是0。
变化后四位妃子的 weight 和 dynamicWeight 值如下：
设置后四位妃子的 weight 和 dynamicWeight 值如下：
如果大家依然还是有点模糊，我们只能上代码为敬了！我们需要先定义一个实体，来存放每个妃子及对应的 weight 及 dynamicWeight 属性：
/**
* *权重实体
*
* @author sullivan
*
*/
public class PrincessWeight {
private String princess;
private Integer weight;
private Integer dynamicWeight;
public PrincessWeight(String princess, Integer weight, Integer dynamicWeight) {
super();
this.princess = princess;
this.weight = weight;
this.dynamicWeight = dynamicWeight;
}
}
然后定义两个全局的对象存放对象：
// 每个妃子及对应的权重实体
private static Map<String, PrincessWeight> weightMap = new HashMap<String, PrincessWeight>();
// 总权重值
private static int totalWeight = 0;
再进行算法的实现：
private static String getPrincess() {
// 初始化妃子及对应的权重实体
if (weightMap.isEmpty()) {
//将配置初始化到map中去
for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
// 算法的第一点：初始dynamicWeight为0
weightMap.put(princess, new PrincessWeight(princess, PrincessConfig.PRINCESS_MAP.get(princess), 0));
totalWeight += PrincessConfig.PRINCESS_MAP.get(princess);
}
}
// 算法的第二点：设置currentWeight=设置weight+currentWeight
for (PrincessWeight weight : weightMap.values()) {
weight.setDynamicWeight(weight.getWeight() + weight.getDynamicWeight());
}
// 算法的第三点：寻找最大的currentWeight
PrincessWeight maxPrincessWeight = null;
for (PrincessWeight weight : weightMap.values()) {
if (maxPrincessWeight == null || weight.getDynamicWeight() > maxPrincessWeight.getDynamicWeight()) {
maxPrincessWeight = weight;
}
}
// 算法的第四点：最大的dynamicWeight = dynamicWeight-totalWeight
maxPrincessWeight.setDynamicWeight(maxPrincessWeight.getDynamicWeight() - totalWeight);
return maxPrincessWeight.getPrincess();
}
最终输出如下：
随机算法
我们依然先定义一个妃子集合如下：
/**
* *所有妃子集合
*/
public static final List<String> PRINCESS_LIST = Arrays.asList("令妃", "娴妃", "高贵妃", "纯妃");
然后利用随机函数去选择一个目标：
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(getPrincess());
}
}
/**
* *随机获取侍寝妃子
* @return
*/
private static String getPrincess() {
SecureRandom rd = new SecureRandom();
int index = rd.nextInt(PrincessConfig.PRINCESS_LIST.size());
return PrincessConfig.PRINCESS_LIST.get(index);
}
加权随机算法
加权随机实现一
加权随机实现一与上面的加权轮询实现一的思路几乎一毛一样，这里就直接上代码了：
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(getPrincess());
}
}
private static String getPrincess() {
List<String> princessList = new ArrayList<String>();
for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
int weight = PrincessConfig.PRINCESS_MAP.get(princess);
for (int i = 0; i < weight; i++) {
princessList.add(princess);
}
}
Random rd = new Random();
int index = rd.nextInt(princessList.size());
return princessList.get(index);
}
加权随机实现二
加权随机实现二与上面的加权轮询实现二的思路几乎一模一样，这里也就直接上代码了：
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(getPrincess2());
}
}
private static String getPrincess2() {
List<String> princessList = new ArrayList<String>();
int totalWeight = 0;
for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
int weight = PrincessConfig.PRINCESS_MAP.get(princess);
totalWeight += weight;
for (int i = 0; i < weight; i++) {
princessList.add(princess);
}
}
Random rd = new Random();
int index = rd.nextInt(totalWeight);
String result = null;
for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
int weight = PrincessConfig.PRINCESS_MAP.get(princess);
// 落在当前区间 直接返回
if (index < weight) {
result = princess;
break;
}
// 没有落在当前区间 继续循环
index = index - weight;
}
return result;
}
源地址 hash 算法
到这里我们也得让我们的皇阿玛歇会儿了，回到我们正常的业务场景中。假如我们有服务器配置如下：
/**
* *所有服务器集合
*/
public static final List<String> SERVER_IP_LIST = Arrays.asList(
"192.168.1.10",
"192.168.2.20",
"192.168.3.30",
"192.168.4.40");
客户端访问的 ip 我也模拟了一个集合：
/**
* *客户端ip
*/
public static final List<String> CLIENT_IP_LIST = Arrays.asList(
"113.88.97.173",
"106.11.154.33",
"207.46.13.149",
"42.156.137.120",
"203.208.60.0",
"119.39.47.182",
"171.34.179.4",
"111.175.58.52",
"124.235.138.199",
"175.184.166.184");
实现如下：
public static void main(String[] args) {
for (String clientIp : CLIENT_IP_LIST) {
int index = Math.abs(getHash(clientIp)) % PrincessConfig.SERVER_IP_LIST.size();
String serverIp = PrincessConfig.SERVER_IP_LIST.get(index);
System.out.println(clientIp + "请求的服务器ip为" + serverIp);
}
}
最终输出如下：
比如我们服务器去掉一台 192.168.4.10 的机器再看下输出结果：
一致性 hash 算法
客户端 ip 进行 hash 后不就是一个 int32 的数字嘛，那我们就可以把一个 int32 的数字分为几个段，让每个服务器负责一个段的请求！
如果客户端 ip 进行 hash 后的值在 0~536870911 之间，那就交给 IP2 服务器处理。
如果客户端 ip 进行 hash 后的值在 536870911~1073741822 之间，那就交给 IP3 服务器处理。
如果客户端 ip 进行 hash 后的值在 1073741822~1610612733 之间，那就交给 IP4 服务器处理。
如果客户端 ip 进行 hash 后的值大于 1610612733 之间，那就交给 IP1 服务器处理。
但是专业一点的表示都会把这个横坐标掰弯，形成一个环，就叫所谓的 hash 环，如下图：
这样对部分客户端的请求依然会有影响，但至少影响也只是局部的，如下图：
每个服务器在 hash 环上的位置是我们人为的均匀的分配的，这样经常需要扩容缩容的时候会不会比较难以维护呢？
IP4 宕机，原本会到 IP4 的请求全部转移到 IP1，那会不会导致 IP1 的流量不均衡？能不能有一个更均衡一点的方案让原本到 IP4 的流量均衡的转移到 IP1、IP2、IP3 呢？
这样存在的一个问题是每个集群的服务器 ip 都会不同，因此计算后落在环上的位置可能就是不可控的。
如下图所示：
讲了这么多，但实现起来也不难，下面就该上代码了（服务器配置及请求的客户端 ip 与源地址 hash 算法部分的一致，这里就不贴对应的代码了，直接上算法逻辑）：
//虚拟结点数量100
private static final Integer VIRTUAL_NODES = 100;
public static void main(String[] args) {
// 遍历服务器ip，生成对应的虚拟结点
TreeMap<Integer, String> nodeMap = new TreeMap<Integer, String>();
for (String serverIp : PrincessConfig.SERVER_IP_LIST) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
nodeMap.put(getHash(serverIp + "VN" + i), serverIp);
}
}
for (String clientIp : CLIENT_IP_LIST) {
//这里利用的TreeMap的特性，不清楚的可以去自己去了解一下tailMap方法的作用
SortedMap<Integer, String> subMap = nodeMap.tailMap(getHash(clientIp));
Integer firstKey = null;
try {
firstKey = subMap.firstKey();
} catch (Exception e) {
}
if (firstKey == null) {
firstKey = nodeMap.firstKey();
}
System.out.println("请求的服务器ip为" + nodeMap.get(firstKey));
}
}
到此，几种常用的负载均衡算法及代码实现都已介绍完毕！还有不清楚可以去同性交友网下载示例代码自己调试：
https://github.com/sujing910206/load-balance
作者：苏静
简介：有过多年大型互联网项目的开发经验，对高并发、分布式、以及微服务技术有深入的研究及相关实践经验。经历过自学，热衷于技术研究与分享！格言：始终保持虚心学习的态度！
编辑：陶家龙、孙淑娟
征稿：有投稿、寻求报道意向技术人请联络 editor@51cto.com
精彩文章推荐：